public class UnionFind {
//    记录连通分量数目
    private int count;
//    记录父节点，起始时都为自身，之后慢慢合并
    private int[] parent;

//    初始化
    public UnionFind(int n) {
        this.count=n;
        parent=new int[n];
        for(int i=0;i<n;i++){
            parent[i]=i;
        }
    }

//    合并两个点，构造（添加）新的集合
    public void union(int p,int q){
//        找到p和q的根节点，也就是属于哪个集合
        int rootP=find(p);
        int rootQ=find(q);
//        相等说明同属一个集合
        if(rootP==rootQ){
            return;
        }
//        以其中一个点当作根（反过来写也行）
        parent[rootP]=rootQ;
//        连通分量-1
        count--;
    }

//    查找某个节点的根节点
    public int find(int x){
//        对于根节点，parent[x]=x
        while (parent[x]!=x){
            x=parent[x];
        }
        return x;
    }

//    返回连通分量个数
    public int getCount() {
        return count;
    }
//    判断两个点是否连通：判断根节点是否相同
    public boolean connected(int p,int q){
        int rootP = find(p);
        int rootQ = find(q);

        return rootP==rootQ;
    }
}
